{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "4e11e651",
   "metadata": {
    "pycharm": {
     "name": "#%% md\n"
    }
   },
   "source": [
    "# 汉诺塔问题hanoi"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "id": "e23dfe2f",
   "metadata": {
    "ExecuteTime": {
     "end_time": "2023-01-03T08:27:50.833261Z",
     "start_time": "2023-01-03T08:27:50.814349Z"
    },
    "pycharm": {
     "name": "#%%\n"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "moving from A to C\n",
      "moving from A to B\n",
      "moving from C to B\n",
      "moving from A to C\n",
      "moving from B to A\n",
      "moving from B to C\n",
      "moving from A to C\n"
     ]
    }
   ],
   "source": [
    "def hanoi(n,a,b,c):\n",
    "    if n>0:\n",
    "        hanoi(n-1,a,c,b)\n",
    "        print('moving from %s to %s'%(a,c))\n",
    "        hanoi(n-1,b,a,c)\n",
    "hanoi(3,'A','B','C')"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "1e195e1b",
   "metadata": {
    "ExecuteTime": {
     "end_time": "2023-01-03T10:06:05.903468Z",
     "start_time": "2023-01-03T10:06:05.896486Z"
    },
    "pycharm": {
     "name": "#%% md\n"
    }
   },
   "source": [
    "# 列表查找"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "bfe7c8f5",
   "metadata": {
    "pycharm": {
     "name": "#%% md\n"
    }
   },
   "source": [
    "## 顺序查找"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "id": "2fcdcd3e",
   "metadata": {
    "ExecuteTime": {
     "end_time": "2023-01-03T10:14:42.467115Z",
     "start_time": "2023-01-03T10:14:42.459137Z"
    },
    "pycharm": {
     "name": "#%%\n"
    }
   },
   "outputs": [],
   "source": [
    "@cal_time\n",
    "def linear_search(li,val):\n",
    "    for ind,v in enumerate(li):\n",
    "        if v==val:\n",
    "            return ind\n",
    "    else:\n",
    "        return None"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "60cdf6bb",
   "metadata": {
    "pycharm": {
     "name": "#%% md\n"
    }
   },
   "source": [
    "## 二分查找"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "id": "cd38f4cc",
   "metadata": {
    "ExecuteTime": {
     "end_time": "2023-01-03T13:15:11.016148Z",
     "start_time": "2023-01-03T13:15:10.996200Z"
    },
    "pycharm": {
     "name": "#%%\n"
    }
   },
   "outputs": [],
   "source": [
    "@cal_time\n",
    "def binary_search(li,val):\n",
    "    left=0\n",
    "    right=len(li)-1\n",
    "    while left<=right:\n",
    "        mid=(left+right)//2\n",
    "        if li[mid]==val:\n",
    "            return mid\n",
    "        elif li[mid]>val:\n",
    "            right=mid-1\n",
    "        elif li[mid]<val:\n",
    "            left=mid+1\n",
    "    else:\n",
    "        return None"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "39b267ff",
   "metadata": {
    "pycharm": {
     "name": "#%% md\n"
    }
   },
   "source": [
    "## 顺序查找和二分查找的比较"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "id": "8b823f90",
   "metadata": {
    "ExecuteTime": {
     "end_time": "2023-01-03T13:15:27.094768Z",
     "start_time": "2023-01-03T13:15:27.084794Z"
    },
    "pycharm": {
     "name": "#%%\n"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3"
      ]
     },
     "execution_count": 29,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "li=list(range(1000))\n",
    "linear_search(li,3)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 37,
   "id": "84c61138",
   "metadata": {
    "ExecuteTime": {
     "end_time": "2023-01-03T13:15:30.984501Z",
     "start_time": "2023-01-03T13:15:30.975528Z"
    },
    "pycharm": {
     "name": "#%%\n"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3"
      ]
     },
     "execution_count": 37,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "li=list(range(1000))\n",
    "binary_search(li,3)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "id": "eb705dbc",
   "metadata": {
    "ExecuteTime": {
     "end_time": "2023-01-03T10:14:50.471051Z",
     "start_time": "2023-01-03T10:14:50.452141Z"
    },
    "pycharm": {
     "name": "#%%\n"
    }
   },
   "outputs": [],
   "source": [
    "#修饰器，计算运行速度\n",
    "import time\n",
    "def cal_time(func):\n",
    "    def wrapper(*args,**kwargs):\n",
    "        t1=time.time()\n",
    "        return func(*args,**kwargs)\n",
    "        t2=time.time()\n",
    "        print('%s running time: %s secs.'%(func.__name__,t2-t1))\n",
    "    return wrapper"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "0da080a3",
   "metadata": {
    "pycharm": {
     "name": "#%%\n"
    }
   },
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "dda14116",
   "metadata": {
    "pycharm": {
     "name": "#%%\n"
    }
   },
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "354a3fcb",
   "metadata": {
    "pycharm": {
     "name": "#%%\n"
    }
   },
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "58a9a968",
   "metadata": {
    "pycharm": {
     "name": "#%%\n"
    }
   },
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "7d59ca94",
   "metadata": {
    "pycharm": {
     "name": "#%%\n"
    }
   },
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.9.7"
  },
  "toc": {
   "base_numbering": 1,
   "nav_menu": {},
   "number_sections": true,
   "sideBar": true,
   "skip_h1_title": false,
   "title_cell": "Table of Contents",
   "title_sidebar": "Contents",
   "toc_cell": false,
   "toc_position": {},
   "toc_section_display": true,
   "toc_window_display": false
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}
